#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode *next;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class kthElement {
    // 递归实现，取巧了，使用了栈使其早break
public:
    int kthSmallest(TreeNode* root, int k) {
        traverse(root, k);
        return sk.top();
    }

    void traverse(TreeNode* root, int k) {
        if (root == nullptr)
            return;
        
        traverse(root->left, k);
        if (sk.size() == k)
            return;
        else sk.push(root->val);
        traverse(root->right, k);
    }

private:
    stack<int> sk;
};

class kthElementNoRecursive {
    // 栈迭代实现，直接返回
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode *> sk;

        while (true) {
            while (root != nullptr) {
                sk.push(root);
                root = root->left;
            }
            root = sk.top();
            sk.pop();
            if (--k == 0)
                return root->val;
            root = root->right;
        }

    }
};



class makeBstToGst {
    // 将搜索树转为累加树，节点值为所有大于其的节点和
    // 使用反向中序遍历，求和更新节点
public:
    TreeNode* bstToGst(TreeNode* root) {
        sum = 0;
        traverse(root);
        return root;
    }

    void traverse(TreeNode *root) {
        if (root == nullptr) 
            return;
        traverse(root->right);
        sum += root->val;
        root->val = sum;
        traverse(root->left);
    }

private:
    int sum;
};